Disjunctive constraints in scheduling

Daniel Gardin Gratti

unread,

Feb 20, 2025, 11:05:21 AMFeb 20

to MiniZinc

Hey, I've been migrating to minizinc recently. While working with models for potentially preemptive scheduling for the job-shop problem I was surprised that the model almost always seems to ignore the disjunctive constraint, even with no preemption. I have tried the following strategies: Given an array of fixed size n of tasks along with an array containing the group (machine) it belongs, to avoid overlapping in a same group (machine), we can formulate the following constraint

constraint forall(p1, p2 in 1..num_parts, i, j in 1..num_group_tasks where (i < j) /\ (group[i] = group[j])) (
(end[group_task[i], p1] <= start[group_task[j], p2]) \/ (end[group_task[j], p2] <= start[group_task[i], p1])
);

or, by using scheduling-specific predicates,

constraint forall(g in 1..num_groups) (
disjunctive([start[group_task[i], 1] | p in 1..num_parts, i in 1..num_group_tasks where group[i] == g],
[duration[group_task[i], 1] | p in 1..num_parts, i in 1..num_group_tasks where group[i] == g])
);

However, any of these seems to be working properly, except sometimes when the tasks are sorted by processing times (working_example.dzn is the only instance that yields non-overlaping tasks). I use a python code to plot a Gantt chart along with the output to check for overlapping tasks more easily:

minizinc --solver cplex model.mzn data.dzn --output-mode json --soln-sep "" --search-complete-msg "" | python gantt.py

I can't find where my model is mistaken, or if I'm doing something wrong in the process. Any ideas on what is possibly broken?

Thank you in advance,

Daniel

PS: After some testing, I found out that ortools correctly behaves, in opposite to cplex and gurobi, when using the disjunctive predicate, isn't it well-defined in cplex and gurobi? Why do they keep ignoring them?

simple_data.dzn

ta01.dzn

gantt.py

model.mzn

working_example.dzn

krzysztof....@gmail.com

unread,

Feb 23, 2025, 1:24:26 PMFeb 23

to MiniZinc

Disjunctive constraint is directly implemented in many CP solvers while in LP solvers it is decomposed to disjunction of inequalities in a similar way as you defined it. Therefore it is always best to use global constraints. Moreover, you should use search annotation to instruct solvers on best search strategy. For example,

solve :: int_search(start, smallest, indomain_min) minimize makespan;

ottools with option -p 16 gives an optimal solution for ta01 data in ~4s. Similar results will be obtained if you use free search (option -f). Other CP solver find solutions but I am not sure if they can get optimal solution in a reasonable time.

Daniel Gardin Gratti

unread,

Feb 26, 2025, 3:45:47 AMFeb 26

to MiniZinc

Thank you for your answer, I didn't know about the search annotation, that's something I'm going to check further.

I just think it's funny that or-tools can find the optimal makespan, 1231, in a reasonable time, but CPLEX, running the same code, totally ignores the disjunctive constraint, returning a makespan of 963. Is there some reason it behaves like that? CPLEX has its own NoOverlap function, but that doesn't seem to be called...

Daniel Gardin Gratti

unread,

Feb 26, 2025, 5:09:06 AMFeb 26

to MiniZinc

Oh never mind, I found the problem. Apparently, the disjunctive constraint was being ignored due to the overflow when the horizon was set to 2147483647, the last 32-bit signed integer.

Reply all

Reply to author

Forward